package Graph.graphWithWeight.MinistedTree.Kruskal;


import Graph.graphWithNoweight.dfs.Graph;
import Graph.graphWithWeight.GraphWeight;

import java.util.ArrayList;

/**
 * @Author: 蔡翔
 * @Date: 2020/2/4 16:30
 * @Version 1.0
 *
 * 求联通分量相关信息
 * 3
 */
public class ConnectComponent {

    private GraphWeight G;
    private int[] visited;
    // 联通分量
    private int cccount=0;

    private ArrayList<Integer> order = new ArrayList<>();

    public ConnectComponent(GraphWeight G){
        this.G = G;
        visited = new int[G.V()];
        for(int i=0;i<G.V();i++){
            visited[i] = -1;
        }

        for(int v=0;v<G.V();v++){
            if(visited[v]==-1){
                dfs(v,cccount);
                //下面的cccount++ 代表 一个连通图 遍历完了，计数+1  开始下一个连通图计数
                cccount++;
            }
        }
    }

    private void dfs(int v,int ccID) {
        visited[v] = ccID;
        order.add(v);
        for(int w:G.adj(v)){
            if(visited[w]==-1){
                dfs(w,ccID);
            }
        }
    }

    public Iterable<Integer> order(){
        return order;
    }

    public boolean isConnected(int v,int w){
        G.validateVertex(v);
        G.validateVertex(w);
        return visited[v] == visited[w];
    }

    public ArrayList<Integer>[] components(){
        ArrayList<Integer>[] res = new ArrayList[cccount];
        for(int i= 0;i<cccount;i++){
            res[i] = new ArrayList<>();
        }

        for(int i=0;i<G.V();i++){
            res[visited[i]].add(i);
        }
        return res;
    }

    public Integer count(){
        for(int e:visited){
            System.out.print(e+"  ");
        }
        System.out.println();

        return this.cccount;
    }
}